1. Field of the Invention
The present invention is generally related to a method and apparatus for acquiring a pseudorandom noise (PN) signal in a receiver. In particular, the present invention relates to methods and apparatus for the fast acquisition and fast correlation of a pseudorandom noise (PN) signal in a Global Positioning System (GPS) receiver.
2. Description of the Related Art
The Global Positioning System (GPS) Operational Constellation nominally consists of 24 earth orbiting satellites. Each satellite radiates a spread spectrum, pseudorandom noise (PN) signal indicating the satellite""s position and time. A GPS receiver tuned to receive the signals from the satellites can compute the distance to the satellites and calculate the receiver""s position, velocity, and time. The receiver calculates the distance to a satellite by multiplying the propagation rate of the satellite""s radio signal (the speed of light) by the time it took the signal to travel from the satellite to the receiver.
Each satellite transmits two carrier signals referred to as L1 and L2. L1 operates at a frequency of 1.57542 GHz and L2 operates at a frequency of 1.22760 GHz. Multiple binary codes induce phase modulation upon the L1 and L2 carrier signals. Each satellite in the GPS Operational Constellation transmits a unique code over the L1 and L2 carrier signals. One of the phase-modulated signals is C/A Code (Coarse Acquisition). Presently, 32 codes are defined for the C/A Code. A satellite""s C/A Code phase modulates the L1 carrier over a 1.023 MHz bandwidth. The C/A Code is a repeating 1023 bit sequence. At 1023 bits and 1.023 MHz, the C/A Code repeats every millisecond. The C/A Code forms the basis for the Standard Positioning Service (SPS) used by civilians.
Another phase-modulated signal is the P-Code (Precise). The P-Code is similar to the C/A Code in that it is a PN sequence which phase modulates a carrier signal. The P-Code modulates both the L1 and the L2 signals at a rate of 10.23 MHz. In an Anti-Spoofing mode, the P-Code is encrypted to produce the Y-Code to restrict access to users with the encryption key. The P-Code forms the basis for the military""s Precise Positioning Service (PPS). One reason the PPS is more accurate than the SPS is that the PPS relies on two signals, L1 and the L2, which operate at different frequencies. Because the L1 and L2 signals have different frequencies, a receiver using both signals can compensate for the distortion in propagation delay induced by ionospheric conditions. In 1998 and 1999, the U.S. Government announced plans to add a second civilian signal to the existing L2 carrier signal and add a third civilian signal to a third carrier at 1.17645 GHz.
In a GPS receiver, xe2x80x9cacquiringxe2x80x9d a satellite occurs when the GPS receiver acquires the signal of a satellite. The GPS receiver acquires the satellite by matching a code received by the GPS receiver to a code defined for the satellite. This matching is termed xe2x80x9ccorrelation.xe2x80x9d Acquiring a satellite as quickly as possible is a highly desirable characteristic, particularly when the GPS receiver operates in an environment featuring interference or obstructions to radio reception. An example is a car moving in canyons, by tall buildings, over bridges, in tunnels, in parking structures, and the like. Under these conditions, reception from a satellite can be sporadic. If the GPS receiver cannot acquire or reacquire a satellite quickly, the GPS system may not be able to provide the user with useful information. To compensate for intermittent reception of the satellite signals, many automotive GPS systems include supplemental inertial navigation systems such as gyroscopes, which increases the cost of the system.
One factor that increases the acquisition time of a system is a frequency error or variance between the frequency transmitted by the satellite and the frequency expected by the GPS receiver. When the frequency received from the satellite varies from the frequency expected by the system, the amount of correlation between the transmitted satellite code and the expected satellite code decreases. A severe reduction in the amount of correlation can result in a failure to acquire the satellite because the system fails to recognize the event as a correlation.
Several sources of error contribute to the frequency error. A crystal oscillator such as a Numerically Controlled Oscillator (NCO), typically controls the frequency of a GPS receiver. Crystal oscillators are notorious for wide frequency variability over temperature, and crystal oscillators often feature heated crystals with well-controlled temperature to stabilize the frequency. The frequency of an oscillator of a receiver is quite unpredictable when the receiver is first turned on. High g loading also induces changes to the frequency of crystal oscillators.
Doppler shift is another source of frequency variance. Unfortunately, in the literature surrounding GPS, the terms Doppler shift or Doppler frequency are often used to refer generically to any deviation in frequency from any source. Relative motion between a transmitter and a receiver introduces Doppler shifts to periodic signals. In a receiver, Doppler shift increases as the differential relative velocity increases and as the frequencies increases. For example, the Doppler shift for the 10.23 MHz P(Y) Code is 10 times worse than the Doppler shift for the 1.023 MHz C/A Code. Doppler shift, if left uncompensated, can limit the data transmission rate of future digital communications systems implemented with spread spectrum technology such as cellular telephones and wireless Internet. In a spread spectrum communications system, the rate of modulation of the code signal is much higher than the rate of modulation of the information signal. A simplified formula approximating Doppler shift of a signal is expressed below:       f    D    =            f      S        ·                  Δ        ⁢                  xe2x80x83                ⁢        v            c      
In the simplified formula expressed above, fD is the Doppler shift, fS is the signal frequency, xcex94v is the difference in relative speed between the transmitter and the receiver, where the relative speed is measured along the axis of propagation of the radio waves emitted by the transmitter, and c is the speed of light. In a sample calculation, a plane moving at a relative velocity towards a satellite at a speed of 1000 miles per hour suffers a 15 Hz Doppler shift in a 10.23 MHz signal. In the GPS constellation, satellites orbit the Earth in low earth orbits and induce a Doppler shift by their own movement as well. The Doppler shift of a signal survives the downconversion in the receiver.
Present methods of compensating for frequency offsets have proven inadequate. Conventional systems acquire the satellite signal by continuously looping and searching for correlation by varying the frequency and the codes. The process of incrementally searching frequencies is very time consuming.
In another conventional system, a Fast Fourier Transform (FFT) is implemented in a circuit to attempt to detect the frequency offset due to oscillator drift or Doppler shift. However, most FFT implementations induce an uneven (sin x)/x response to the frequency domain magnitude. The uneven response of a coherently integrated FFT results in correlation loss in the presence of a frequency offset induced by oscillator drift or Doppler shift. Present methods of compensating for the uneven frequency response of a coherently integrated FFT rely on software, thereby creating heavy processing loads on the CPU. Ironically, the FFT is intended to reduce processing loads on the CPU.
The present invention solves these and other problems by allowing spread spectrum receivers to quickly acquire a pseudorandom noise signal. In one embodiment, the receiver advantageously detects frequency shifts using a compact parallel process hardware implementation of a Discrete Fourier Transform (DFT). The simultaneous detection of multiple frequencies allows the receiver to search a larger frequency range of the transmitted signal, thereby increasing the speed of acquisition. One embodiment does not use coherent integration before computation of the transform and advantageously maintains a flat frequency response. The flat frequency response of the DFT enables searching of multiple frequency offsets without CPU-intensive processing to compensate for frequency response variations. In one embodiment, the DFT uses an implementation of a Coordinate Rotation Digital Computer (CORDIC) to perform the complex number multiplication. A receiver according to an embodiment of the invention can further include a Doppler correction circuit, which permits correlation data with frequency shift in the code to be non-coherently integrated among relatively fewer addresses or tap positions in memory.
One embodiment uses a complex number multiplier that simultaneously computes multiple products of a complex number multiplicand. In one embodiment, the complex number multiplier multiplies the complex number substantially in compliance with a CORDIC algorithm, where a complex number is multiplied by rotations of angles having arctangents of powers of 2. The complex number multiplier produces products, which are rotated relative to the multiplicand within a first range.
The multiple products produced by the complex number multiplier allow a circuit computing a DFT to select a product rather than compute the product. In one embodiment, the circuit produces rotations greater than the 90-degree first range by additional 90, 180, and 270-degree rotations.
The multiple products produced by the complex number multiplier advantageously allows multiple DFT frequency bins to select products from the complex number multiplier rather than having the multiple DFT frequency bins individually compute the product. The result is a large saving in circuitry when a DFT is implemented in hardware.
In one embodiment, a receiver combines the complex number multiplier with input memory to reduce the amount of total system memory. The input memory can include integration. By storing the input to the DFT in an input memory, and accessing the input memory by data samples which are of different sample periods but in the same relative position within the period, the embodiment advantageously allows the DFT to store the computation result directly sample point by sample point, as opposed to sequence by sequence.
One system further staggers the start and stop times of coherent integration of different frequency bins and clears individual memory locations of coherent integration memory as the memory locations are read. The stagger and clearing allow the system to reuse magnitude computation circuits and continue to accumulate coherent data without employing expensive double buffered memory.
One receiver includes a Doppler offset generator that can advantageously offset a time index used to address a tap position in a non-coherent memory to compensate for code drift in a code with a frequency offset. The amount of offset is computed by accumulating clock cycles of a clock signal that is related to the frequency offset computed by the DFT or FFT frequency bin. The offset aligns a correlation peak in the received code such that the correlation peak can be accumulated in relatively fewer tap positions or addresses.